﻿namespace ProblemsSet
{
    public class Problem_70 : BaseProblem
    {
        public override object GetResult()
        {
            const int max = 10000000;

            var res = double.MaxValue;
            long val = 0;

            for(var n = max; n > 1; n--)
            {
                if (n / (double)(n - 9) > res) break;

                var tmp = MathLogic.Phi(n);

                var q = n / (double)tmp;
                if (q >= res) continue;

                if (MathLogic.GetHashOfDigits(n) != MathLogic.GetHashOfDigits(tmp)) continue;

                res = q;
                val = n;
            }
            return val;
        }

        public override string Problem
        {
            get
            {
                return @"Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1  n  107, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 8319823;
            }
        }
    }
}
